function popSort(arr) {
    if(!arr ||!arr.length){
        return;
    }
    let len = arr.length;
    for (let i = 0; i < len -1; i++) {//i 控制冒泡的轮次,对于len的数组，只需要冒泡len-1次
        for (let j = 0; j < len-i -1; j++) {//j控制对比的下标
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}


/* 选择排序 */
function selectionSort(array){
    if(!array ||!array.length){
        return;
    }
    let length = array.length,indexMin;
    for (let i=0; i<length-1; i++){//i表示需要查找的次数，length的数组需要查找的次数是length-1
        indexMin = i;
        for (let j=i+1; j<length; j++ ){ //j表示每次查找的元素下标
            if (array[indexMin] > array[j]){
                indexMin = j
            }
        }
        if(indexMin !== i){
            let temp = arr[indexMin];
            arr[indexMin] = arr[i];
            arr[i] = temp;
        }
    }
}

let arr1 = [2,7,8,0,-1,9,3,3];
popSort(arr1);
console.log(arr1);
let arr2 = [];
popSort(arr2);
console.log(arr2);
let arr3 = undefined;
popSort(arr3);
console.log(arr3);

console.log('selectionSort------------------')
arr = [2,7,8,0,-1,9,3,6,3];
console.log(arr);
selectionSort(arr)
console.log(arr);


function insertSort(array){
    if(!array ||!array.length){
        return;
    }
    let length = array.length;
    for (let i=1; i<length; i++){//i表示需要插入的次数，length的数组需要查找的次数是length-1
        let temp = array[i];
        for (let j=i-1; j>=0; j-- ){ //j表示每次查找的元素下标
            if (array[j] > temp){
                array[j+1] = array[j]
            }else {
                array[j+1] = temp;
                break;//插入完成跳出循环
            }

        }
    }
}


// this.insertionSort = function(){
//     let len = array.length,j,temp;
//     //j 就是当前排序数组里面的最大值。
//     for (let i = 1; i < len; i++) {
//         temp = array[i];
//         j = i;
//         while (j > 0 && array[j -1] > temp) {
//             array[j] = array[j -1];
//             j -- ;
//         }
//         array[j] = temp
//     }
// };

console.log('insertSort------------------')

arr = [-1, 0, 2, 3, 3, 7, 8, 9,6];
console.log(arr);
insertSort(arr)
console.log(arr);

console.log('mergeSort------------------')
function mergeSort(array){
    if(!array ||!array.length){
        return;
    }
    if(array.length === 1){
        return array;
    }
    let minI = Math.floor(array.length/2);
    let leftArr = array.slice(0,minI);
    let rightArr = array.slice(minI,array.length);
    return mergeArr(mergeSort(leftArr),mergeSort(rightArr));

}
function mergeArr(leftArr,rightArr){
    let li = 0,ri = 0;
    let result = [];
    while (li < leftArr.length && ri < rightArr.length) {
        if(leftArr[li] < rightArr[ri]){
            result.push(leftArr[li++]);
        }else {
            result.push(rightArr[ri++]);
        }
    }
    while(li < leftArr.length){
        result.push(leftArr[li++])
    }
    while(ri < rightArr.length){
        result.push(rightArr[ri++])
    }
    return result;
}
arr = [-1, 0, 2, 3, 3, 7, 8, 9,6,10,4];
console.log(mergeSort(arr))


